import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/10 9:36
 * @description 迭代
 */
public class Solution2 {
    public static void main(String[] args) {

    }
    public List<Integer> preorder(Node root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Deque<Node> deque = new ArrayDeque<>();
        deque.push(root);
        while (!deque.isEmpty()) {
            Node temp = deque.pop();
            ans.add(temp.val);
            for (int i = temp.children.size() - 1; i >=0 ; i--) {
                deque.push(temp.children.get(i));
            }
        }
        return ans;
    }
}
